package interview.Datastructures;
import java.util.*;

class Graph{
	public static void dfs(int[][] graph, int source, int dest) {
		int pathLength =0;
		ArrayList<Integer> path = new ArrayList<Integer>();
		Stack<Integer> exploredVertex = new Stack<Integer>();
		exploredVertex.push(new Integer(source));
		boolean pushed;
		boolean seen=false;
		boolean[] markedVertices = new boolean[graph.length];
		while(!exploredVertex.empty()){
			pushed = false;
			int element = (int)exploredVertex.peek();
			path.add(element);
			pathLength++;
			if (element == dest)
				{   seen = true;
					break;
				}
			markedVertices[element]=true;			
			for(int i=0; i<graph.length;i++){
				if((graph[element][i]==1) && (!markedVertices[i])){
					if (i == dest)
					{   seen = true;
						break;
					}
					exploredVertex.push(new Integer(i));
					pushed = true;
				}				
			}
			if (seen)break;
			if(!pushed) {
				exploredVertex.pop();
				path.remove(--pathLength);
			}
		}
		if (seen)
			System.out.println(path);
		
		else
			System.out.println("Not found");
	}

	public static void bfs(int[][] graph, int source, int dest) {
		int pathLength =0;
		ArrayList<Integer> path = new ArrayList<Integer>();
		Queue exploredVertex = new Queue();
		boolean enqueued=false;
		boolean seen=false;
		boolean[] markedVertices = new boolean[graph.length];
		exploredVertex.enqueue(source);
		while(!exploredVertex.isEmpty()){
			seen=false;
			int element = exploredVertex.dequeue();
			path.add(element);
			markedVertices[element]=true;
			if (element==dest) {   
				seen = true;
				break;
			}
			for(int i=0; i<graph.length;i++){
				if((graph[element][i]==1) && (!markedVertices[i])){
					if (i == dest)
					{   seen = true;
						break;
					}
					exploredVertex.enqueue(i);
					enqueued = true;					
				}				
			}
			if (seen)
				break;
			if(!enqueued) {
				exploredVertex.dequeue();
				path.remove(--pathLength);
			}
		}
		if (seen)
			System.out.println(path);
		
		else
			System.out.println("Not found");
		
	}
	
	
}


public class GraphTest {
	public static void main(String ... args){
		int[][] testGraph = {
								{1,1,1,0,1,0,0},
								{1,1,1,1,0,0,0},
								{1,1,1,0,0,1,0},
								{0,1,0,1,0,0,1},
								{1,0,0,0,1,1,0},
								{0,0,1,0,1,1,1},
								{0,0,0,1,0,1,1}
							};
		Graph.dfs(testGraph,6,0);	
		Graph.bfs(testGraph,6,0);
		}
}

